package structure.stack;

/**
 * 栈内的元素以链表形式存放的栈
 */
class CustomLinkedStack {
    private CustomLinkedList list;

    CustomLinkedStack() {
        list = new CustomLinkedList();
    }

    /**
     * 将指定元素压入栈顶部（链表索引值为0的位置）
     * @param element
     */
    void push(Object element) {
        list.addFirst(element);
    }

    /**
     * 弹出栈顶部的元素（链表内第一个元素）
     * @return 被弹出的元素
     */
    Object pop() {
        structure.stack.CustomLinkedStack.CustomLinkedList.CustomLinkedListNode node = list.removeFirst();
        if (node != null) {
            return node.getData();
        } else {
            return null;
        }
    }

    /**
     * 链栈内存放元素的链表
     */
    private class CustomLinkedList {
        private CustomLinkedListNode head;
    
        CustomLinkedList() {
            head = new CustomLinkedListNode(null);
        }
    
        /**
         * 在链表的索引值为0的位置添加节点
         * @param element
         */
        private void addFirst(Object element) {
            CustomLinkedListNode first = new CustomLinkedListNode(element);
            CustomLinkedListNode temp = head;
            first.setNext(temp.getNext());
            temp.setNext(first);
        }
    
        /**
         * 移除链表中的首个节点
         * @return 被移除的元素
         */
        private CustomLinkedListNode removeFirst() {
            if (this.isEmpty()) {
                return null;
            } else {
                CustomLinkedListNode node = head.getNext();
                head.setNext(node.getNext());
                return node;
            }
        }
    
        /**
         * 判断链表是否为空
         * @return 如果链表为空，则返回true
         */
        private boolean isEmpty() {
            CustomLinkedListNode node = head.getNext();
            return node == null;
        }

        /**
         * 记录链表内每个节点的数据域与链域
         */
        class CustomLinkedListNode {
            private Object element;
            private CustomLinkedListNode next;
        
            Object getData() {
                return element;
            }
        
            CustomLinkedListNode getNext() {
                return next;
            }
        
            void setNext(CustomLinkedListNode next) {
                this.next = next;
            }
        
            CustomLinkedListNode(Object element) {
                this.element = element;
                next = null;
            }
        }
    }
}
